import java.util.Arrays;
import java.util.PriorityQueue;

public class TopK {
    public static int[] find1(int[] array,int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //O(n*logN)
        for (int i = 0; i < array.length; i++) {
            minHeap.offer(array[i]);
        }
        //k*logN
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    public static int[] find2(int[] array, int k) {
        // 建大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)-> b - a);
        //k*logN
        for (int i = 0; i < k; i++) {
            maxHeap.offer(array[i]);
        }
        for(int i = k; i < array.length; i++) {
            int top = maxHeap.peek();
            if(top > array[i]) {
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {1,3,5,7,2,4,6,8};
        int[] ret1 = find1(array,4  );
        int[] ret2 = find2(array,4  );
        System.out.println(Arrays.toString(ret1));
        System.out.println(Arrays.toString(ret2));
    }
}
